package Leetcode.排序;

import java.util.Random;

/**
 * @ClassName pub
 * @since: 2023/9/14 20:39
 * @auth: kirito
 * @description:
 **/
public class SortUtils {
    /**
     * 交换数组的对应位置
     * @param arr
     * @param a1
     * @param a2
     */
    public static void swap(int[] arr,int a1, int a2) {
        int temp = arr[a1];
        arr[a1] = arr[a2];
        arr[a2] = temp;

    }

    public static void swap(Integer[] arr,int a1, int a2) {
        int temp = arr[a1];
        arr[a1] = arr[a2];
        arr[a2] = temp;
    }

    /**
     * 自动生成随机数组
     * @param N 数组长度
     * @param min   最小值
     * @param max   最大值
     * @return
     */
    public static Integer[] generateRandomArray(int N, int min, int max) {
        Integer[] arr = new Integer[N];
        Random r = new Random();
        for (int i = 0; i < N; i++) {
            arr[i] = min + r.nextInt(max - min + 1);
        }
        return arr;
    }
    public static int[] generateRandomArray_int(int N, int min, int max) {
        int[] arr = new int[N];
        Random r = new Random();
        for (int i = 0; i < N; i++) {
            arr[i] = min + r.nextInt(max - min + 1);
        }
        return arr;
    }

    /**
     * 打印二维数组（不限制方阵）
     * @param arr 二维数组
     */
    public static void printArr(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                System.out.printf("%4d", arr[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 荷兰国旗问题
     */
    public void sortColors(int[] nums) {
        int index0 = 0;               // 用于放置 0 的指针
        int index2 = nums.length - 1; // 用于放置 2 的指针
        int i = 0;                    // 当前遍历指针

        while (i <= index2) {         // 遍历到 index2 为止
            if (nums[i] == 0) {
                swap(nums, index0, i); // 交换 0 到左边
                index0++;
                i++;                  // 继续处理下一个元素
            } else if (nums[i] == 2) {
                swap(nums, index2, i); // 交换 2 到右边
                index2--;             // 收缩右边界

                // 注意这里并不知道2换来的是什么，所以要停留一下。
            } else {
                i++;                  // 跳过 1
            }
        }
    }

    /**
     * 一个不含重复数字的正整数数组  将其划分为两半，使其左和与右和的绝对值之差最大
     * 快排思想
     */
    public int MaxSumDiff(int[] arr) {
        int n = arr.length;
        int pri, low = 0, low_temp = 0, height = n - 1, height_temp = n - 1;
        boolean flag = true;
        int k = n / 2;
        while (flag) {
            pri = arr[low];
            while (low < height) {
                while (low < height && arr[height] >= pri) {
                    height--;
                }
                if (low != height) {
                    arr[low] = arr[height];
                }
                while (low < height && arr[low] <= pri) {
                    low++;
                }
                if (low != height) {
                    arr[height] = arr[low];
                }
            }
            arr[low] = pri;
            if (low == k - 1) {
                flag = false;
            } else {
                if (low < k - 1) {
                    low_temp = ++low;
                    height = height_temp;
                } else {
                    height_temp = --height;
                    low = low_temp;
                }
            }
        }
        int sum1 = 0, sum2 = 0;
        for (int i = 0; i < k; i++) {
            sum1 += arr[i];
        }
        for (int i = k; i < n; i++) {
            sum2 += arr[i];
        }
        return sum2 - sum1;
    }
    //[2, 3, 4, 5, 6, 7, 8]
    //9--26
    public static void main(String[] args) {
        int[] arr = {3, 7, 5, 6, 4, 2, 8};
        SortUtils test = new SortUtils();
        System.out.println(test.MaxSumDiff(arr));

    }

}
